package com.congee02;

public class MergeKLists_Naive_Merge {

    public ListNode mergeKLists(ListNode[] lists) {
        int n;
        if (lists == null || (n = lists.length) == 0) {
            return null;
        }
        if (n < 2) {
            return lists[0];
        }
        ListNode merged = merge(lists[0], lists[1]);
        for (int i = 2 ; i < n ; i ++ ) {
            merged = merge(merged, lists[i]);
        }
        return merged;
    }

    private ListNode merge(ListNode l1 , ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode p1 = l1;
        ListNode p2 = l2;

        final ListNode sentinel = new ListNode(-1);
        ListNode add = sentinel;

        ListNode step;
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                step = p1.next;
                add.next = p1;
                p1 = step;
            } else {
                step = p2.next;
                add.next = p2;
                p2 = step;
            }
            add = add.next;
        }

        while (p1 != null) {
            step = p1.next;
            add.next = p1;
            add = add.next;
            p1 = step;
        }

        while (p2 != null) {
            step = p2.next;
            add.next = p2;
            add = add.next;
            p2 = step;
        }

        return sentinel.next;
    }

}
